// https://leetcode.cn/problems/minimum-window-substring/description/

// 算法思路总结：
// 1. 滑动窗口寻找覆盖目标字符的最小子串
// 2. 使用哈希表统计目标字符出现次数
// 3. 维护窗口内有效字符种类计数
// 4. 收缩窗口优化最小长度并保持覆盖
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm>
#include <climits>

class Solution 
{
public:
    string minWindow(string s, string t) 
    {
        int m = s.size(), n = t.size();
        int hash1[128] = {0}, hash2[128] = {0};

        int kind = 0;
        for (const char& ch : t)
        {
            if (hash2[ch] == 0)
            {
                kind++;
            }
            hash2[ch]++;
        }

        int begin = -1, minLen = INT_MAX;
        for (int l = 0, r = 0, count = 0 ; r < m ; r++)
        {
            char in = s[r];
            if (++hash1[in] == hash2[in])
            {
                count++;
            }
            while (count == kind)
            {
                if (r - l + 1 < minLen)
                {
                    begin = l;
                    minLen = r - l + 1;
                }
                
                char out = s[l++];
                if (hash1[out]-- == hash2[out])
                {
                    count--;
                }
            }    
        }

        return begin == -1 ? "" : s.substr(begin, minLen);
    }
};

int main()
{
    string s1 = "ADOBECODEBANC", t1 = "ABC";
    string s2 = "a", t2 = "aa";

    Solution sol;

    cout << sol.minWindow(s1, t1) << endl;
    cout << sol.minWindow(s2, t2) << endl;

    return 0;
}